常用算法策略之回溯法

发表于 | 分类于 | 阅读次数

1.回溯法简介

回溯法，又称试探法，是常用的，基本的优选搜索方法。常用于解决这一类问题：给定一定约束条件F（该约束条件常用于后面的剪枝）下求问题的一个解或者所有解。

回溯法其实是暴力枚举的一种改进，因为其会聪明的filter掉不合适的分支，大大减少了无谓的枚举。若某问题的枚举都是可行解得话，也就是没有剪枝发生，那么回溯法和暴力枚举并无二异。

该回溯法先从解空间中选取任意一个可能满足约束条件F的点x1,然后从满足F的解空间中继续选择一个点x2，直到所找到的点构成一个解S或者找不到满足约束条件F的点时，开始回溯。回溯到上一层节点f，再另选满足F的解空间中的一点，继续试探。

整个过程类似于一个递归树，因此回溯法常常采用DFS的方法来实现。不考虑约束条件F，整个递归树的任一根节点root到叶子节点leaf的路径path都是无约束条件F的原问题的一个解。

现在考虑约束条件F，实际就是在每次向下深入的时候，利用约束条件F来判断当前遍历的节点是否有必要继续搜索下去,若无必要则马上回溯；有必要则继续深入，这一个过程类似于约束条件F剪去了多余的递归分支。

回溯法解决的问题的一般特征：能够利用约束条件F去快速判断构成一个完整解的一些局部候选信息partial candidates是否可能最终构成一个正确的、完整的解。

2.回溯法的基本步骤

  1. 明确问题的解空间S和约束条件F.
  2. 利用深度优先搜索，试探可能构成一个完整解的候选节点，利用约束条件F进行剪枝
    2.1. 找到递归的base case
    2.2. 利用约束条件F判断是否剪枝，一旦剪枝，则开始回溯（返回）
  3. 当递归到叶节点的时候，即得到原问题在约束条件F下的一个解，若要得到所有的可行解，则还需要考察根节点的其他分支。

回溯法注意事项：

  1. 递归状态的存储和更新
  2. 回溯点的处理（是否应该清除该回溯点之前对递归状态产生的side effect）
  3. 解的搜集

3.回溯法之经典问题

回溯法之经典问题：N皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class NQueensDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		NQueensDemo demo = new NQueensDemo();
		demo.solution(8);
	}

	public void solution(int n) {
		List<int[]> collector = new ArrayList<>();
		for (int j = 0; j < n; j++)
			dfs(0, j, new int[n], new int[n], new int[n], new int[n * 2 - 1], new int[n * 2 - 1], collector, n);
		System.out.println("numbers of solution " + collector.size());
		print(collector, n);
	}

	public void dfs(int i, int j, int[] solution, int[] occupiedRow, int[] occupiedCol, int[] occupiedTopBottom,
			int[] occupiedBottomTop, List<int[]> collector, int size) {
		solution[i] = j;
		if (i >= size - 1) {
			collector.add(solution.clone());
			return;
		}

		// 8个方向
		occupiedRow[i] = 1;
		occupiedCol[j] = 1;
		occupiedTopBottom[size - 1 + (i - j)] = 1;// 左上到右下的斜线 (i+d, j+d) 关系为i-j,
													// 范围为 -size + 1 ~ size - 1,
													// 所以左右各加size - 1归到区间
													// 0~2size - 2, 关系为 size - 1
													// + (i - j), 分配的数组大小为 2size
													// - 1
		occupiedBottomTop[i + j] = 1;// 左下到右上的斜线(i-d, j+d)和(i+d, j-d) 关系为 i+j
										// 分配的数组大小为 2size - 1

		// 寻找下一个皇后放置的位置
		i = i + 1;
		for (int n = 0; n < size; n++) {
			if (occupiedRow[i] == 0 && occupiedCol[n] == 0 && occupiedTopBottom[size - 1 + (i - n)] == 0
					&& occupiedBottomTop[i + n] == 0)
				dfs(i, n, solution, occupiedRow, occupiedCol, occupiedTopBottom, occupiedBottomTop, collector, size);
		}

		// 回溯后, clear flag，恢复原状
		i = i - 1;
		occupiedRow[i] = 0;
		occupiedCol[j] = 0;
		occupiedTopBottom[size - 1 + (i - j)] = 0;
		occupiedBottomTop[i + j] = 0;
	}

	public void print(List<int[]> collector, int n) {
		for (int[] s : collector) {
			System.out.println();
			for (int i = 0; i < n; i++) {
				System.out.println();
				for (int j = 0; j < n; j++) {
					if (j == s[i])
						System.out.print(1 + "  ");
					else
						System.out.print(0 + "  ");
				}
			}
		}
	}

}

4.回溯法之经典问题：Sudoku（数独）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

public class Solution {
   public final char base = '1';
	public void solveSudoku(char[][] board) {
		int filledNum = 0;// 统计已填的数目，作为DFS搜索结束的条件
		int m = 0, n = 0;
		int[][] rowCount = new int[9][9], colCount = new int[9][9], subBoxCount = new int[9][9];

		for (m = 0; m < 9; m++)
			for (n = 0; n < 9; n++)
				if (board[m][n] != '.') {
					rowCount[m][board[m][n] - base] += 1;
					colCount[n][board[m][n] - base] += 1;
					subBoxCount[m / 3 * 3 + n / 3][board[m][n] - base] += 1;
					filledNum++;
				}

		boolean found = false;
		for (m = 0; m < 9; m++) {// 找到第一个待填的方格
			for (n = 0; n < 9; n++)
				if (board[m][n] == '.') {
					found = true;
					break;
				}
			if (found)
				break;
		}

		for (int num = 0; num < 9; num++)
			if (rowCount[m][num] == 0 && colCount[n][num] == 0 && subBoxCount[m / 3 * 3 + n / 3][num] == 0)
				if (dfs(m, n, (char) (num + base), board, rowCount, colCount, subBoxCount, filledNum))
					break;
	}

	public boolean dfs(int i, int j, char c, char[][] board, int[][] rowCount, int[][] colCount, int[][] subBoxCount,
			int filledNum) {

		int number = c - base;// 0~8代表1~9
		board[i][j] = c;
		rowCount[i][number] += 1;
		colCount[j][number] += 1;
		subBoxCount[i / 3 * 3 + j / 3][number] += 1;
		filledNum += 1;

		// bas case
		if (filledNum >= 81)
			return true;

		int m = i, n = j;
		boolean found = false;
		// 找到下一个待填方格
		for (; m < 9; m++) {
			for (; n < 9; n++) {
				if (board[m][n] == '.') {
					found = true;
					break;
				}
			}
			if (found)
				break;
			else
				n = 0;
		}

		for (int num = 0; num < 9; num++) {
			if (rowCount[m][num] == 0 && colCount[n][num] == 0 && subBoxCount[m / 3 * 3 + n / 3][num] == 0) {
				if (dfs(m, n, (char) (num + base), board, rowCount, colCount, subBoxCount, filledNum))
					return true;
			}
		}

		// failed 该格子无论填啥都无解,所以clear所做的更改
		board[i][j] = '.';
		rowCount[i][number] -= 1;
		colCount[j][number] -= 1;
		subBoxCount[i / 3 * 3 + j / 3][number] -= 1;
		filledNum -= 1;

		return false;
	}
}